import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int len = strs.length;

        //key 为 strs 中的元素，value 为将 key 中的字符按字典序排序后的结果
        Map<String, String> map1 = new HashMap<>();

        //key 为 字典序字符串，value 为异位词集合
        Map<String, List<String>> map2 = new HashMap<>();

        //key 为 strs 中的元素，value 为对应的个数
        Map<String, Integer> map3 = new HashMap<>();

        List<String> list1 = new ArrayList<>();

        for (int i = 0; i < len; i++) {
            map3.put(strs[i], map3.getOrDefault(strs[i], 0) + 1);
            char[] ch = strs[i].toCharArray();
            Arrays.sort(ch);
            map1.put(strs[i], new String(ch));
            map2.put(new String(ch), new ArrayList<>());
        }

        for (Map.Entry<String, String> entry : map1.entrySet()) {
            List<String> list = map2.get(entry.getValue());
            int count = map3.get(entry.getKey());
            while (count > 0) {
                list.add(entry.getKey());
                count--;
            }
            // list.add(entry.getKey());
        }

        List<List<String>> ret = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : map2.entrySet()) {
            ret.add(entry.getValue());
        }

        if (list1.size() > 0) {
            ret.add(list1);
        }

        return ret;
    }
}